Stack

Let’s learn about stacks in Go.

Introduction#

The stack is a data structure that operates on the last-in-first-out (LIFO) principle. This means that the elements that we inserted last would be removed first.

Applications of stacks#

The stack is used in a wide variety of applications, including:

  • Implementation of recursive calls.
  • Postfix evaluation of an expression.
  • Backtracking.
  • Depth-first search of trees and graphs.
  • Converting a decimal to a binary number, and so on.

Stack ADT Operations#

  • Push(k) pushes a value k to the top of the stack.
  • Pop() removes an element from the top of the stack and return its value.
  • Top() returns the value of the element on top of the stack.
  • Size() returns the number of elements in the stack.
  • IsEmpty() tells us whether the stack is empty or not. If the stack is empty, it returns true. Otherwise, it returns false.

Note: All of the above operations are implemented in O(1)O(1) time complexity.

To see how stacks work, let’s look at the illustration below:

Created with Fabric.js 3.6.6 1 2 3 top Top value is 3 at the start

1 of 3

Created with Fabric.js 3.6.6 1 2 3 4 top New value pushed on top which is 4

2 of 3

Created with Fabric.js 3.6.6 1 2 3 top popped 4 which was on top

3 of 3

Example#

Stack is implemented in Go as follows:

We’ll learn about stacks in detail in a later chapter.

Go Collection Framework

Queue